Complex base systems

In arithmetic, a complex base system is a positional numeral system whose radix is an imaginary (proposed by Donald Knuth in 1955^[1]^[2]) or complex number (proposed by S. Khmelnik in 1964^[3] and Walter F. Penney in 1965^[4]^[5]).

1 In general
2 Binary systems
3 Base −1±i
4 See also
5 References
6 External links

In general

Let $D$ be an integral domain $\subset \C$ and $|\cdot|$ the (Archimedean) absolute value on it.

A number $X\in D$ in this positional number system is represented as an expansion

$X = \sum_{\nu}^{ } x_\nu \rho^\nu$ , where

$\rho$ – the radix (or base) $\in D$ with $|\rho|>1$ ,
$\nu$ – exponent (position or place) $\in \Z$
$x_\nu$ – digits from the finite set of digits $Z \subset D$ usually with $|x_\nu| < |\rho|$ . The cardinality $R:=|Z|$ is called the level of decomposition.

A positional number system or coding system is a pair

$\left\langle \rho, Z \right\rangle$

with radix $\rho$ and set of digits $Z$ , and we write the standard set of digits with $R$ digits as

Failed to parse (unknown function\dotsc): Z_R := \{0, 1, 2,\dotsc, {R-1}\}

Desirable are coding systems with the features

Every number in $D$ , e. g. the Gaussian integers $\Z[\mathrm i]$ , is uniquely representable as a finite code, possibly with a sign.
Every number in $\C$ is representable as an infinite code, where the series $X$ converges under $|\cdot|$ for $\nu \to -\infty$ , and the measure of the set of numbers with more than 1 representation is 0. The latter requires that the set $Z$ be minimal, i. e. $R=|\rho|^2$ .

In this notation our standard decimal coding scheme is denoted by

$\left\langle 10, Z_{10} \right\rangle$ ,

the standard binary system is

$\left\langle 2, Z_2 \right\rangle$ ,

the negabinary system is

$\left\langle -2, Z_2 \right\rangle$ ,

and the balanced ternary system^[2] is

$\left\langle 3, \{-1,0,1\} \right\rangle$ .

All these coding systems have the mentioned features for $\Z$ and $\R$ , and the latter two do not require a sign.

Well-known positional number systems for the complex numbers include the following ( $\mathrm i$ being the imaginary unit):

$\left\langle\sqrt{R},Z_R\right\rangle$ , e. g. $\left\langle\pm \mathrm i \sqrt{2},Z_2\right\rangle$ ^[1] and

$\left\langle\pm 2\mathrm i,Z_4\right\rangle$ , ^[2] the quater-imaginary base, proposed by Donald Knuth in 1955.

$\left\langle\sqrt{2}e^{\pm \tfrac{\pi}2 \mathrm i}=\pm \mathrm i\sqrt{2},Z_2\right\rangle$ and

$\left\langle\sqrt{2}e^{\pm \tfrac{3 \pi}4 \mathrm i}=-1\pm\mathrm i,Z_2\right\rangle$ ^[3]^[4] (see also the section Base −1± $\mathrm i$ below).

$\left\langle\sqrt{R}e^{\mathrm i}\varphi,Z_R\right\rangle$ , where $\varphi=\pm \arccos{(-\beta/(2\sqrt{R}))}$ , $\beta<\min(R, 2\sqrt{R})$ and $\beta_{ }^{ }$ is a positive integer that can take multiple values at a given $R$ .^[6] For $\beta=1$ and $R=2$ this is the system

$\left\langle\tfrac{-1%2B\mathrm i\sqrt7}2,Z_2\right\rangle$ .

$\left\langle 2e^{\tfrac{\pi}3 \mathrm i},A_4:=\left\{0,1,e^{\tfrac{2 \pi}3 \mathrm i},e^{-\tfrac{2 \pi}3 \mathrm i}\right\}\right\rangle$ ;^[7]

$\left\langle-R,A_R^2\right\rangle$ , where the set $A_R^2$ consists of complex numbers $r_\nu=\alpha_\nu^1%2B\alpha_\nu^2\mathrm i$ , and numbers $\alpha_\nu^{ } \in Z_R$ , e. g.

$\left\langle -2, \{0,1,\mathrm i,1%2B\mathrm i\}\right\rangle$ .^[7]

$\left\langle\rho=\rho_2,Z_2\right\rangle$ , where $\rho_2=\begin{cases} (-2)^{\tfrac{\nu}2} & \text{if } \nu \text{ even,}\\ (-2)^{\tfrac{\nu-1}2}\mathrm i & \text{if } \nu \text{ odd.} \end{cases}$ ^[8]

Binary systems

Binary coding systems of complex numbers, i. e. systems with the digits $Z_2=\{0,1\}$ , are of practical interest.^[8] Listed below are some coding systems $\langle \rho, Z_2 \rangle$ (all are special cases of the systems above) and codes for the numbers –1, 2, -2, $\mathrm i$ . The standard binary (which requires a sign) and the negabinary systems are also listed for comparison. They do not have a genuine expansion for $\mathrm i$ .

radix	$-1$	$2$	$-2$	$\mathrm i$	twins and triplets ¹
$2$	$-1$	$10$	$-10$	$\mathrm i$	0.1 = 1.0 = 1
$-2$	$11$	$110$	$10$	$\mathrm i$	0.01 = 1.10 = $\tfrac13$
$\textstyle \mathrm i\sqrt 2$	$101$	$10100$	$100$	$10.101010100010...$	0.0011 = 11.1100 = $\tfrac13%2B\tfrac13\mathrm i\sqrt 2$
$-1%2B\mathrm i$	$11101$	$1100$	$11100$	$11$	0.010 = 11.001 = 1110.100 = $\tfrac15%2B\tfrac35\mathrm i$
$\tfrac{-1%2B\mathrm i\sqrt7}2$	$111$	$1010$	$110$	$11.110001100111...$	1.011 = 11.101 = 11100.110 = $\tfrac{3%2B\mathrm i\sqrt7}4$
$\rho_2$	$101$	$10100$	$100$	$10$	0.0011 = 11.1100 = $\tfrac13%2B\tfrac13\mathrm i$
¹ the underline marks the period

As in all positional number systems with an Archimedean absolute value there are some numbers with multiple representations. Examples of such numbers are shown in the right column of the table.
If the set of digits is minimal, the set of such numbers has a measure of 0. This is the case with all the mentioned coding systems.

Base −1±i

Of particular interest, the quater-imaginary system, and base -1±i systems discussed below can be used to finitely represent the Gaussian integers without sign.

Base −1±i, using digits 0 and 1, was proposed by S. Khmelnik in 1964^[3] and Walter F. Penney in 1965.^[5] The rounding region of an integer – i.e., a set of complex (non-integer) numbers that share the integer part of their representation in this system – has a fractal shape, the twindragon.

References

^ ^a ^b Knuth, D.E. (1960). "An Imaginary Number System". Communication of the ACM-3 (4).
^ ^a ^b ^c Knuth, Donald (1998). "Positional Number Systems". The art of computer programming. Volume 2 (3rd ed.). Boston: Addison-Wesley. pp. 205. ISBN 0-201-89684-2. OCLC 48246681.
^ ^a ^b ^c Khmelnik, S.I. (1964 (see also here)). "Specialized digital computer for operations with complex numbers". Questions of Radio Electronics (in Russian) XII (2).
^ ^a ^b Jamil, T. (2002). "The complex binary number system". IEEE Potentials 20 (5): 39–41. doi:10.1109/45.983342.
^ ^a ^b Duda, Jarek (2008-02-24). "Complex base numeral systems". arXiv:0712.1309.
^ Khmelnik, S.I. (1966 (see also here)). "Positional coding of complex numbers". Questions of Radio Electronics (in Russian) XII (9).
^ ^a ^b Khmelnik, S.I. (2004 (see also here)). Coding of Complex Numbers and Vectors (in Russian). «Mathematics in Computers», Israel, ISBN 978-0-557-74692-7.
^ ^a ^b Khmelnik, S.I. (2001). Method and system for processing complex numbers. Patent USA, US2003154226 (A1). http://worldwide.espacenet.com/publicationDetails/biblio?DB=EPODOC&adjacent=true&locale=en_EP&FT=D&date=20030814&CC=US&NR=2003154226A1&KC=A1.

External links

"Number Systems Using a Complex Base" by Jarek Duda, the Wolfram Demonstrations Project
"The Boundary of Periodic Iterated Function Systems" by Jarek Duda, the Wolfram Demonstrations Project
"Number Systems in 3D" by Jarek Duda, the Wolfram Demonstrations Project